package edu.siu.math.egut.util;

import java.io.Serializable;
//import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.WeakHashMap;
import java.util.Map.Entry;



//import com.sun.tools.javac.util.List;
//import edu.siu.math.egut.egut.Algorithms;


/**
 * The Class Polynomial is a representation of the mathematical object of the
 * same name. This class is a simple way to store pairs of integer coefficients
 * with the corresponding monomials. This class uses a store of polynomials so
 * that there is at most one of each polynomial at a time. This should reduce
 * the amount of memory used in large scale applications. This class is heavily
 * based on a similar program written in C++ by Joseph Hundley.
 * 
 * 
 * @author Joe Pleso
 * 
 */
public final class LaurentPolynomial implements Serializable {
    /**
     * 
     */
    private static final long serialVersionUID = 220L;

    /**
     * Returns a polynomial for roots suitable for TeX'ing.
     * 
     * @param root root from G2
     * @return TeX poly
     */
    public static LaurentPolynomial rootToPolynomial (int[] root){
	if (root.length != 2)
	    throw new RuntimeException("Only G2 supported!");
	LaurentPolynomial alpha = create("\\alpha");
	LaurentPolynomial beta = create("\\beta");
	LaurentPolynomial result = alpha.times(root[0]);
	return result.plus(beta.times(root[1]));
    }
    
    
    private static final Map<LaurentPolynomial, Object> polynomials = 
	new WeakHashMap<LaurentPolynomial, Object>();
    
    /**
     * Creates a polynomial with only a constant term.
     * 
     * @param constant           the constant to be represented as a polynomial
     * @return polynomial with only a constant term
     */
    public static LaurentPolynomial create(Integer constant) {

	Map<Term, Integer> t = new HashMap<Term, Integer>();
	if (constant != 0)
	    t.put(Term.create((Map<String,Integer>)new HashMap<String,
		    Integer>()), constant);
	for (LaurentPolynomial p : polynomials.keySet()) {
	    if (p.terms.equals(t))
		return p;
	}
	return new LaurentPolynomial(t);
    }

    
    
    /**
     * Creates a polynomial that has only has one term.
     * 
     * @param coefficient                the coefficient to the only term
     * 
     * @param mono                the only term in the polynomial
     * @return a polynomial that has only the specified term
     */
    public static LaurentPolynomial create(Integer coefficient, Term mono) {

	Map<Term, Integer> t = new HashMap<Term, Integer>();
	if (coefficient != 0)
	    t.put(mono, coefficient);
	for (LaurentPolynomial p : polynomials.keySet())
	    if (p.terms.equals(t))
		return p;
	return new LaurentPolynomial(t);

    }

    /**
     * Default way to create a polynomial. Takes a map with monomials and the
     * corresponding coefficients. Returns the specified polynomial.
     * 
     * @param arg            the map containing the monomials and their
     *  coefficients
     * @return the polynomial containing the specified monomials and
     *         coefficients
     */
    public static LaurentPolynomial create(Map<Term, Integer> arg) {
	for (LaurentPolynomial p : polynomials.keySet())
	    if (p.terms.equals(arg))
		return p;

	return new LaurentPolynomial(arg);
    }
  
    /**
     * Create the polynomial that consists of a single variable.
     * 
     * @param var1               the name of the variable
     * @return the polynomial equal to 1 * var1 ^ 1
     */
    public static LaurentPolynomial create(String var1) {

	SortedMap<String, Integer> preMonomial = new TreeMap<String, Integer>();
	// Map used to construct monomial

	preMonomial.put(var1.intern(), 1);
	Term r = Term.create(preMonomial);
	return create(1, r);

    }

    /*
     * Tries to parse a string into a polynomial,
     * interpreting +, -, * and ^ as algebraic operations, 
     * sequences of digits which begin the string or 
     * follow an algebraic operator are interpreted 
     * as numbers.  All other characters are lumped together
     * into String variable names.
     * (Note that this includes parentheses.)
     * 
     * @param s A string
     *                
     * @return a polynomial interpretation of s.
     * @throws LaurentPolynomialReadException 
     *  
     */
     /*public static LaurentPolynomial read(String s) throws 
      * LaurentPolynomialReadException  {

	 
	 LaurentPolynomial p = create(0);//start with the zero polynomial
	 
	 while (!(s.length()==0)){ //do this until we run out of string
	 
	     s = s.trim();
	      //remove trailing/leading whitespace
	     
	     
	     int lastPlus = s.lastIndexOf(Algorithms.LIE_PLUS);
	     int lastMinus = s.lastIndexOf(Algorithms.LIE_MINUS);
	     
	     int breakPoint = Math.max(lastPlus, lastMinus);
	     //this is where we want to split
	     
	     String t;
	     if (breakPoint == -1){
		 t = s;
		 s = "";
	     }else{
	     t = s.substring(breakPoint);//this is the current term
	     s = s.substring(0, breakPoint);//this is what is left over
	     }
	     
	     t = t.trim();
	      //remove trailing whitespace
	     
	     boolean isNegative = t.charAt(0) == Algorithms.LIE_MINUS;
	     //get the sign of the term
	     
	     if (t.charAt(0) == Algorithms.LIE_PLUS
	 
	     || t.charAt(0) == Algorithms.LIE_MINUS)
		 t = (t.substring(1)).trim(); //strip sign off if necessary
	     
	     int i = 0;
	     for (; i < t.length(); i++){
		 if (!Character.isDigit(t.charAt(i)))
		     break;
	     }//find the end of the coeff
	     
	     int coeff;
	     if (i == 0){
		 coeff = 1;
	     }else{
		coeff  = Integer.parseInt(t.substring(0, i)); 
	     }
	      
	     t = (t.substring(i)).trim();//what's left is the monomial
	     
	     try {
		if (isNegative)

		    p = p.minus(create(coeff, Term.read(t)));

		else
		    p = p.plus(create(coeff, Term.read(t)));
	     } catch (TermReadException e) {
		    throw new LaurentPolynomialReadException(e);
		    
		}
	   
	 }
	 return p;

    }*/

    private final TreeMap<Term, Integer> terms;

    private LaurentPolynomial(Map<Term, Integer> arg) {

	for (Integer i : arg.values())
	    if (i == 0)
		throw new IllegalArgumentException();
	terms = new TreeMap<Term, Integer>(arg);
	polynomials.put(this, null);
    }

    /**
     * This method factors out a variable from the polynomial. That is the
     * result is the sum of each monomial in this polynomial that is not
     * independent of the named variable after it has been factored out. (Note:
     * this only seems to make sense if this is true of all monomials, even
     * though this condition is not checked!)
     * 
     * @param name       the name of the variable to be factored out
     * 
     * @return the polynomial which would be the quotient after dividing by the
     *         named variable
     */
    public LaurentPolynomial divide(String name) {
	Map<Term, Integer> answer = new HashMap<Term, Integer>();
	for (Map.Entry<Term, Integer> i : terms.entrySet())
	    if (!(i.getKey().getExponent(name) == 0))
		try {
		    answer.put(i.getKey().factorOut(name), i.getValue());
		} catch (TermVariableMissingException e) {

		    e.printStackTrace();
		    throw new RuntimeException("this shouldn't happen");
		}

	return create(answer);
    }

    /**
     * Gets the number of monomials in this polynomial.
     * 
     * @return the number of monomials in this polynomial
     */
    public int getNumberOfTerms() {
	return terms.size();
    }

    /**
     * Determines the degree in a particular variable, i.e., the highest power
     *  of that variable which appears.
     * @param s String, interpreted as a variable
     * @return 0 if the String does not appear, or the highest power of the
     *  string which does appear.
     */
    public int degreeIn(String s){
	int answer = 0;
	for(Term m: terms.keySet())
	    answer = Math.max(answer, m.degreeIn(s));
	return answer;
	    
    }
    
    /**
     * Returns the set of terms in the polynomial.
     * 
     * @return the set of terms in the polynomial
     */
    public Set<Map.Entry<Term, Integer>> getTerms() {
	return terms.entrySet();
    }
    
    

    /**
     * Checks if the polynomial is independent of a certain variable. This
     * implies that each composing monomial of this polynomial is independent of
     * the named variable.
     * 
     * @param name            of the variable to check
     * @return true, if the polynomial is independent of the named variable
     */
    public boolean isIndependentOf(String name) {

	for (Term m : terms.keySet()) {

	    if (!(m.getExponent((name)) == 0))
		return false;
	}
	return true;
    }

    /**
     * Convenience class for plus.
     * 
     * @param a             the integer to be subtracted
     * @return the polynomial after subtraction has been performed
     */
    public LaurentPolynomial minus(int a) {
	return this.plus(-a);
    }

    /**
     * Subtracts a monomial from this polynomial.
     * 
     * 
     * @param m                the monomial
     * @return the difference
     */
    public LaurentPolynomial minus(Term m) {
	LaurentPolynomial p = this;
	return p.plus(create(-1, m));
    }

    /**
     * Performs this-b.
     * 
     * 
     * @param b              the polynomial (the one subtracting)
     * @return this-b, the difference of the specified polynomials
     */
    public LaurentPolynomial minus(LaurentPolynomial b) {
	LaurentPolynomial a = this;
	return (a.plus(b.times(-1)));
    }

    /**
     * Add a constant to the polynomial.
     * 
     * @param i            the constant
     * 
     * @return the sum
     */
    public LaurentPolynomial plus(Integer i) {
	LaurentPolynomial p = this;
	return p.plus(create(i));
    }

    /**
     * Adds the monomial to this polynomial.
     * 
     * @param m            the monomial
     * 
     * @return the sum
     */
    public LaurentPolynomial plus(Term m) {
	LaurentPolynomial p = this;
	return p.plus(create(1, m));

    }

    /**
     * Adds the two polynomials together. This method is nondestructive in that
     * it returns a new polynomial and leaves the arguments unchanged.
     * 
     * 
     * @param b           the polynomial to be added
     * 
     * @return the sum of the two polynomials
     */
    public LaurentPolynomial plus(final LaurentPolynomial b) {

	LaurentPolynomial a = this;
	if (a.terms.isEmpty() || b.terms.isEmpty())
	    return a.terms.isEmpty() ? b : a;

	Map<Term, Integer> p = new HashMap<Term, Integer>(a.terms);
	for (Map.Entry<Term, Integer> entry : b.terms.entrySet()) {

	    if (!p.containsKey(entry.getKey()))
		p.put(entry.getKey(), entry.getValue());
	    else {
		Integer newCoefficient = entry.getValue()
			+ p.get(entry.getKey());
		if (newCoefficient == 0)
		    p.remove(entry.getKey());
		else
		    p.put(entry.getKey(), newCoefficient);
	    }
	}

	return create(p);
    }

    /**
     * Raises a polynomial to a certain power. The result is returned in a new
     * polynomial. This will throw an IllegalArgumentException if power is less
     * than zero.
     * 
     * 
     * 
     * @param power           the power to raise this polynomial to
     * 
     * @return a new polynomial which contains the result of this polynomial
     *         raised to the specified power
     */
    public LaurentPolynomial raiseTo(int power) {

	LaurentPolynomial p = this;

	if (power == 1)
	    return p;
	if (power == 0)
	    return LaurentPolynomial.create(1);
	if (power < 0 && this.getNumberOfTerms() != 1)
	    throw new IllegalArgumentException();
	if ((power < 0 && this.getNumberOfTerms() == 1)){
	    return this.inverse().raiseTo(-power);
	}
	LaurentPolynomial result = p;
	for (power--; power > 0; power--) {
	    result = result.times(p);
	}
	return result;
    }

    /**
     * Removes the specified term.
     * 
     * @param m the term to be removed
     * @return the polynomial with the term removed 
     */
    public LaurentPolynomial remove(Term m) {

	LaurentPolynomial p = this;

	Map<Term, Integer> t = new HashMap<Term, Integer>(p.terms);
	t.remove(m);
	return create(t);
    }

    /**
     * This method replaces all instances of a variable with a polynomial. The
     * result is stored in a new polynomial, and neither this nor the
     *  replacement
     * polynomial is modified.
     * 
     * @param varName the variable to be replaced
     * @param replacement the polynomial that will replace the variable
     * @return the polynomial where the replacement has occurred
     */
    public LaurentPolynomial replace(final String varName, 
	    final LaurentPolynomial replacement) {
	LaurentPolynomial result = LaurentPolynomial.create(0);
	/*
	System.out.println("Replacing " + varName);
	System.out.println("With " + replacement);
	System.out.println("In " + this);
	*/
	for (Map.Entry<Term, Integer> entry : terms.entrySet()) {
	    if (!(entry.getKey().getExponent(varName) == 0)) {
		
		
		result = result.plus(
			(replacement.raiseTo(entry.getKey().getExponent(varName))
			.times(

			entry.getKey().remove(varName)))
			.times(entry.getValue()));// entry.getValue 
		//= coefficient of the monomial entry...
		/*System.out.println(result);*/
	    }
	    else {
		result = result.plus(
			LaurentPolynomial.create(entry.getValue()).times(
			entry.getKey()));
	    }
	}
	/*System.out.println("Result " + result);*/
	return result;
    }

    
    /**
     * Returns the numerator when the rational function 
     * r = p/q is substituted for the 
     * variable s throughout. 
     * 
     * Concretely, if called by the polynomial a0 + a1 s + ... + aN s^N, returns
     * a0 q^N + a1 p q^(N-1) + ... + aN p^N.
     * @param s string, interpreted as variable name
     * @param r rational function 
     * @return see above.
     */
  /*  public LaurentPolynomial ratlFcnReplaceNum(final String s, 
   * final RationalFunction r){
	LaurentPolynomial result = this; 
	int d = this.degreeIn(s);
	for (Map.Entry<Term, Integer> entry : terms.entrySet()) {
		result = result.remove(entry.getKey());
		result = result.plus(

		(r.getNumerator().raiseTo(entry.getKey().getExponent(s))
			.times(

			entry.getKey().remove(s)))
			.times(entry.getValue()).times(r.getDenominator().
			raiseTo(d - entry.getKey().degreeIn(s))));// entry.
			getValue = coefficient of the monomial entry...
	    
	}
	return result;

    }
    
    
    public RationalFunction replace( final String s, final RationalFunction r){
	return new RationalFunction( this.ratlFcnReplaceNum(s, r), 
	r.getDenominator().raiseTo(this.degreeIn(s)));
    }*/
    
 /*   /** 
     * Destructive replacement.  This method replaces all instances of a 
     * variable with 
     * a polynomial.  The operation is done on the polynomial itself.  
     * @param varName variable to be replaced
     * @param replacement polynomial which is substituted for the variable
     */
 /*   public void replaceDestructive( final String varName, final Polynomial 
  * replacement) {
	for (Map.Entry<Monomial, Integer> entry : terms.entrySet()) {
	    if ((entry.getKey().getExponent(varName) != 0)) {
		int c= entry.getValue(); // coefficient
		int e = entry.getKey().getExponent(varName);// exponent
		Monomial m = entry.getKey().remove(varName); // rest of
		 monomial...
		remove(entry.getKey());
		plus(replacement.raiseTo(e).times(m).times(c));
		

	    }// end if ! exponent(varName) = 0
	    
	}// end for entry from entrySet
    }*/
    
    /**
     * Returns the degree of the polynomial.  (Maximum of the degrees
     *  of its monomial terms.)
     * @return int equal to the degree of the polynomial.
     */
    public int getDegree(){
	return terms.lastKey().getDegree();// order on terms ensures
	//that last is maximal degree.
    }
    
    /**
     * Returns a variable (String) which appears in the Polynomial,
     *  or null if the Polynomial is constant
     * @return a variable (String) which appears in the Polynomial,
     *  or null if the Polynomial is constant
     */
    public String getVar(){
	return terms.lastKey().getVar();
    }
    
    /**
     * Creates Polynomial corresponding to the given monomial
     *  (with coefficient 1).
     * 
     * @param m monomial
     * @return m, regarded as a polynomial with coefficient 1.
     */
    public static LaurentPolynomial create(Term m) {
	return create(1,m);
   }

    /**
     * Multiply a polynomial by a scalar. The result is returned, and the
     * polynomial is unaltered.
     * 
     * @param scalar          the scalar to multiply the polynomial with
     * 
     * @return the scalar product
     */
    public LaurentPolynomial times(int scalar) {

	LaurentPolynomial poly = this;

	if (poly.terms.isEmpty())
	    return this;
	Map<Term, Integer> result = new HashMap<Term, Integer>();
	if (scalar != 0)
	    for (Map.Entry<Term, Integer> entry : poly.terms.entrySet()) {
		result.put(entry.getKey(), entry.getValue() * scalar);
	    }
	return create(result);
    }

    /**
     * Multiply this polynomial by a monomial.
     * 
     * 
     * @param b               the monomial to be multiplied
     * @return the product
     */
    public LaurentPolynomial times(Term b) {

	LaurentPolynomial a = this;
	if (a.terms.isEmpty())
	    return a;
	if (b.getSize() == 0)
	    return a;

	Map<Term, Integer> t = new HashMap<Term, Integer>();

	for (Map.Entry<Term, Integer> eB : a.terms.entrySet()) {
	    t.put(b.multiply(eB.getKey()), eB.getValue());

	}
	return create(t);
    }

    /**
     * Multiply two polynomials. The result is stored in a new polynomial, and
     * the arguments are untouched.
     * 
     * @param b             the other factor
     * 
     * @return the polynomial that is the product of the two factors
     */
    public LaurentPolynomial times(

    final LaurentPolynomial b) {

	final LaurentPolynomial a = this;
	if (a.terms.isEmpty() | b.terms.isEmpty())
	    return a.terms.isEmpty() ? a : b;
	LaurentPolynomial result = LaurentPolynomial.create(new HashMap<Term,
		Integer>());
	for (Map.Entry<Term, Integer> eA : a.terms.entrySet()) {
	    result = result
		    .plus((((b.times(eA.getKey())).times(eA.getValue()))));
	}
	return result;
    }

    /**
     * Returns a string representation of this polynomial.
     * 
     * 
     * @return the polynomial as a string
     */
    public String toString() {

	LaurentPolynomial p = this;
	if (p.terms.isEmpty())
	    return "0";

	StringBuffer sb = new StringBuffer();
	for (Map.Entry<Term, Integer> m : p.terms.entrySet()) {

	    if (m.getValue() >= 0)

		sb.append("+");

	    if (m.getValue() == -1)

		sb.append("-");

	    if (m.getValue() != -1 && m.getValue() != 1)

		sb.append(m.getValue());

	    if (m.getKey().getSize() != 0)

		sb.append(m.getKey().toString());
	    if (m.getKey().getSize() == 0
		    && (m.getValue() == 1 || m.getValue() == -1))
		sb.append("1");
	}

	return sb.charAt(0) == '+' ? sb.substring(1, sb.length()) : sb
		.toString();
    }



    /**
     * Returns the inverse of the Laurent polynomial (if it exists).
     * 
     *  @return the inverse of the Laurent polynomial (if it exists).
     */
    public LaurentPolynomial inverse() {

	if (terms.size() == 1 && (terms.get(terms.firstKey()) == 1
		|| terms.get(terms.firstKey()) == -1))
	return create(terms.get(terms.firstKey()),terms.firstKey().inverse());
	throw new RuntimeException(this + " does not have an inverse.");
    }
    
    
    /**
     * Super crude form of log. Assumes f is a rational function with
     * one variable, one numerator term, and one denominator term.
     * 
     * @param f the function
     * @return the exponent of the variable
     */
    public static int log (LaurentPolynomial f){
	if (f.terms.isEmpty())
	    return 0;
	String x = f.terms.firstKey().getVar();
	if (x==null)
	    
	    return 0;
	    
	//Variable.Local<Rational> x = (Local<Rational>) f.getVariables().
	//get(0);
	//int n = f.getDividend().getOrder(x);
	//int d = f.getDivisor().getOrder(x);
	//return n-d;
	return f.terms.firstKey().degreeIn(x);
    }



    /**
     * Returns the set of variables which appear in the polynomial.
     * 
     * @return the set of variables which appear in the polynomial
     */
    public Set<String> getVariables() {
	TreeSet<String> ts = new TreeSet<String>();
	
	for (Entry<Term, Integer> t : terms.entrySet()){
	    ts.addAll(t.getKey().getVariables());
	}
	return ts;
    }



    /**
     * Convenience to inverse.
     * 
     * @param polynomial the polynomial to take the inverse of
     * @return the product of this and the inverse of the specified polynomial
     */
    public LaurentPolynomial divide(LaurentPolynomial polynomial) {
	
	return this.times(polynomial.inverse());
    }



    /**
     * Returns a term from the polynomial.
     * 
     * @return a term from the polynomial
     */
    public Term getTerm() {

	return terms.firstKey();
    }



    /**
     * Returns the polynomial such that it plus this equals the
     * additive identity.
     * 
     * @return the polynomial such that it plus this equals the
     * additive identity
     */
    public LaurentPolynomial opposite() {
	TreeMap<Term, Integer> tm = new TreeMap<Term,Integer>();
	for (Map.Entry<Term,Integer> e : terms.entrySet()){
	    tm.put(e.getKey(),-e.getValue());
	}
	return create(tm);
    }



    /**
     *Returns the coefficient of the specified term.
     * 
     * @param t the term
     * @return the coefficient of the specified term.
     */
    public Integer getCoefficient(Term t) {
	return terms.get(t);
	
    }
    

    /**
     * used to test if powers work.
     * 
     * @param args ignored
     */
    public static void main (String[] args) {
	LaurentPolynomial y = LaurentPolynomial.create("y");
	LaurentPolynomial u = LaurentPolynomial.create("u");
	LaurentPolynomial z = LaurentPolynomial.create("z");
	LaurentPolynomial test = y.plus(u.times(z));
	for (int power = 0; power < 5; power++) {
	    System.out.println(test.raiseTo(power));
	}
    }
    
    
    
    
    
    
    
}
